1389D - Segment Intersections - CodeForces Solution

// Problem: D. Segment Intersections
// Contest: Codeforces - Educational Codeforces Round 92 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1389/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define bit(x) (1LL << (x))
#define lowbit(x) (x & (-x))
#define SQU(x) ((x) * (x))
#define ls id << 1
#define rs id << 1 | 1
//#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int inv2 = (mod + 1) / 2;
ll qpow(ll x,int y) {
    ll res = 1;
    while(y) {
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
void add(int &x,int y) {
    x += y;
    if(x >= mod) x -= mod;
}
const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
void solve() {
	ll n,k;cin >> n >> k;
	ll l1,r1,l2,r2;
	cin >> l1 >> r1 >> l2 >> r2;
	if(l1 > l2) {
		swap(l1,l2);
		swap(r1,r2);
	}else if(l1 == l2 && r1 > r2) swap(r1,r2);
	auto intersec = [&] (ll l,ll r,ll L,ll R) {
		return max(0LL,min(R,r) - max(l,L) + 1);
	};
	ll s = intersec(l1,r1,l2,r2);
	ll sum = n * (s - 1),ans = 0;
	if(sum >= k) cout << "0\n";
	else if(s != 0) {
		ll mx = max(r1,r2) - min(l1,l2);
		s--;
		if(mx * n >= k) cout << k - sum << '\n';
		else {
			ans += (mx - s) * n;
			k -= mx * n;
			ans += k * 2;
			cout << ans << '\n';
		}
	}else {
		ll d;	
	    if (r1 <= l2){	
	    	d = l2 - r1;	
	    } else {	
	        d = l1 - r2;	
	    }	
	    ans = 1LL << 60;	
	    for (int j = 1; j <= n; j++){	
	        long long tmp = d * j;	
	        long long M = max(r1, r2) - min(l1, l2);	
	        if (k <= M * j){	
	    	    tmp += k;	
	        } else {	
	    		tmp += M * j + (k - M * j) * 2;	
	        }	
        	ans = min(ans, tmp);	
    	}
    	cout << ans << endl;
	}
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int T = 1;
    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}
/*
*/